package org.algorithm.YaYa.链表;

import org.algorithm.common.ListNode;

/**
 * good luck guys
 * keep learing for algorithm
 *
 * @Link {https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/}
 * 反转链表思路：3 -> 5 -> 1 -> 4 -> 9 -> null
 * 反转后：null<- 3 <- 5 <- 1 <- 4 <- 9
 * 链表反转的本质其实就是把每一个节点原本指向下一个节点的next的指针，反转过来指向它的前置节点。进行链表反转的时候，需要同时知道三个节点才能进行反转。
 * 假设：p1  p2  p3,代表例子中3、5、1，以P2为根节点，找到指向P3的next指针反转，此时p2指向p3的指针就变成p2指向p1的
 * 重复上面操作，把p1、p2、p3向后移动一个，再如此一个一个反转即可
 */
public class 反转链表 {
    public static void main(String[] args) {
        ListNode node = ListNode.build(3,5,1,4,9);
        ListNode.print(reverseList(node));
    }

    public static ListNode reverseList(ListNode node) {
        if (null == node || node.next == null) {
            System.out.println("此链表不能进行反转");
            return node;
        }

        ListNode p1 = node;
        ListNode p2 = node.next;
        ListNode p3 = null;
        while (p2 != null) {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        node.next = null;
        node = p1;
        return node;
    }
}
